|
In mathematics, a recurrent word or sequence is an infinite word over a finite alphabet in which every factor occurs infinitely often.〔Lothaire (2011) p. 30〕〔Allouche & Shallit (2003) p.325〕〔Pytheas Fogg (2002) p.2〕 An infinite word is recurrent if and only if it is a sesquipower.〔Lothaire (2011) p. 141〕〔Berstel et al (2009) p.133〕 A uniformly recurrent word is a recurrent word in which for any given factor ''X'' in the sequence, there is some length ''n''''X'' (often much longer than the length of ''X'') such that ''X'' appears in ''every'' block of length ''n'':〔〔Berthé & Rigo (2010) p.7〕〔Allouche & Shallit (2003) p.328〕 the term minimal sequence is also used.〔Pytheas Fogg (2002) p.6〕 ==Examples== * The easiest way to make a recurrent sequence is to form a periodic sequence, one where the sequence repeats entirely after a given number ''m'' of steps. Such a sequence is in then uniformly recurrent and ''n''''X'' can be set to any multiple of ''m'' that is larger than twice the length of ''X''. A recurrent sequence that is ultimately periodic is purely periodic.〔 * The Thue–Morse sequence is uniformly recurrent ''without'' being periodic, nor even eventually periodic (meaning periodic after some nonperiodic initial segment).〔Lothaire (2011) p.31〕 * More generally, all Sturmian words are recurrent.〔Berthé & Rigo (2010) p.177〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Recurrent word」の詳細全文を読む スポンサード リンク
|